package org.example.myleet.p558;

public class Solution {
    public Node intersect(Node quadTree1, Node quadTree2) {
        mergeNode2ToNode1Dfs(quadTree1, quadTree2);
        return quadTree1;
    }

    /**
     * 将树1节点和树2节点做并集，向树1节点并过去
     * 方法是将同一层级的节点分别做并集，分治思想
     */
    public void mergeNode2ToNode1Dfs(Node quadNode1, Node quadNode2) {
        if (quadNode1.isLeaf && quadNode2.isLeaf) {
            //树1节点和树2节点都是叶子节点，则并集取最大的
            if (quadNode2.val) {
                quadNode1.val = true;
            }
            return;
        }
        if (quadNode2.isLeaf) {
            //树2节点是叶子节点，若树2节点的值为1，则树1节点也为1且变成叶子节点
            if (quadNode2.val) {
                quadNode1.val = true;
                quadNode1.isLeaf = true;
                quadNode1.topLeft = null;
                quadNode1.topRight = null;
                quadNode1.bottomLeft = null;
                quadNode1.bottomRight = null;
            }
            return;
        }
        if (quadNode1.isLeaf) {
            //树1节点是叶子节点，若树1节点是1，则全为1；否则，将树2节点复制过来
            if (quadNode1.val) {
                return;
            }
            quadNode1.isLeaf = false;
            quadNode1.val = true;
            quadNode1.topLeft = quadNode2.topLeft;
            quadNode1.topRight = quadNode2.topRight;
            quadNode1.bottomLeft = quadNode2.bottomLeft;
            quadNode1.bottomRight = quadNode2.bottomRight;
            return;
        }
        //树1节点和树2节点都不是叶子节点，分治
        mergeNode2ToNode1Dfs(quadNode1.topLeft, quadNode2.topLeft);
        mergeNode2ToNode1Dfs(quadNode1.topRight, quadNode2.topRight);
        mergeNode2ToNode1Dfs(quadNode1.bottomLeft, quadNode2.bottomLeft);
        mergeNode2ToNode1Dfs(quadNode1.bottomRight, quadNode2.bottomRight);
        //最后进行树1节点的检查，如果是全为1，则标记为叶子节点
        if ((quadNode1.topLeft.isLeaf && quadNode1.topLeft.val) && (quadNode1.topRight.isLeaf && quadNode1.topRight.val) && (quadNode1.bottomLeft.isLeaf && quadNode1.bottomLeft.val) && (quadNode1.bottomRight.isLeaf && quadNode1.bottomRight.val)) {
            quadNode1.isLeaf = true;
            quadNode1.val = true;
            quadNode1.topLeft = null;
            quadNode1.topRight = null;
            quadNode1.bottomLeft = null;
            quadNode1.bottomRight = null;
            return;
        }
        //如果是全为0，也标记为叶子节点
        if ((quadNode1.topLeft.isLeaf && !quadNode1.topLeft.val) && (quadNode1.topRight.isLeaf && !quadNode1.topRight.val) && (quadNode1.bottomLeft.isLeaf && !quadNode1.bottomLeft.val) && (quadNode1.bottomRight.isLeaf && !quadNode1.bottomRight.val)) {
            quadNode1.isLeaf = true;
            quadNode1.val = false;
            quadNode1.topLeft = null;
            quadNode1.topRight = null;
            quadNode1.bottomLeft = null;
            quadNode1.bottomRight = null;
        }
    }
}
